package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-19
 */

/**
 *
 给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：

 二叉树的根是数组 nums 中的最大元素。
 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
 返回有给定数组 nums 构建的 最大二叉树 。
 */
public class leetcode654 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums,0,nums.length-1);
    }
    public TreeNode dfs(int[] nums,int left,int right){
        if (left>right) return null;
        int max = nums[left], index = left;
        for (int i = left+1; i <= right; i++) {
            if (nums[i]>max) {
                max = nums[i];
                index = i;
            }
        }
        TreeNode root = new TreeNode(max);
        root.left = dfs(nums,left,index-1);
        root.right = dfs(nums,index+1,right);
        return root;
    }
}
